// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software for any purpose
// with or without fee is hereby granted, provided that the above copyright notice
// and this permission notice appear in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
// OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

use std::cmp::Ordering;
use std::collections::BinaryHeap;

const NUM_TEST_VALUES: usize = 10000;

/// A wrapper for `i32` to implement `Ord` for min-heap behavior.
#[derive(Eq, PartialEq)]
struct MinHeapItem(i32);

impl Ord for MinHeapItem {
    fn cmp(&self, other: &Self) -> Ordering {
        other.0.cmp(&self.0) // Reverse order for min-heap
    }
}

impl PartialOrd for MinHeapItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// A wrapper for `i32` to implement `Ord` for max-heap behavior.
#[derive(Eq, PartialEq)]
struct MaxHeapItem(i32);

impl Ord for MaxHeapItem {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.cmp(&other.0) // Normal order for max-heap
    }
}

impl PartialOrd for MaxHeapItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[test]
fn test_binary_heap_new_free() {
    for _ in 0..NUM_TEST_VALUES {
        let heap: BinaryHeap<MinHeapItem> = BinaryHeap::new();
        // No explicit free needed in Rust; ownership handles cleanup.
    }

    // Test low memory scenario (not directly applicable in Rust's safe memory model).
}

#[test]
fn test_binary_heap_insert() {
    let mut heap: BinaryHeap<MinHeapItem> = BinaryHeap::new();
    let mut test_array = [0; NUM_TEST_VALUES];

    for i in 0..NUM_TEST_VALUES {
        test_array[i] = i as i32;
        heap.push(MinHeapItem(test_array[i]));
    }

    assert_eq!(heap.len(), NUM_TEST_VALUES);
}

#[test]
fn test_min_heap() {
    let mut heap: BinaryHeap<MinHeapItem> = BinaryHeap::new();
    let mut test_array = [0; NUM_TEST_VALUES];

    for i in 0..NUM_TEST_VALUES {
        test_array[i] = i as i32;
        heap.push(MinHeapItem(test_array[i]));
    }

    let mut i = -1;
    while let Some(MinHeapItem(val)) = heap.pop() {
        assert_eq!(val, i + 1);
        i = val;
    }

    assert_eq!(heap.len(), 0);
    assert_eq!(heap.pop(), None);
}

#[test]
fn test_max_heap() {
    let mut heap: BinaryHeap<MaxHeapItem> = BinaryHeap::new();
    let mut test_array = [0; NUM_TEST_VALUES];

    for i in 0..NUM_TEST_VALUES {
        test_array[i] = i as i32;
        heap.push(MaxHeapItem(test_array[i]));
    }

    let mut i = NUM_TEST_VALUES as i32;
    while let Some(MaxHeapItem(val)) = heap.pop() {
        assert_eq!(val, i - 1);
        i = val;
    }
}

#[test]
fn test_out_of_memory() {
    let mut heap: BinaryHeap<MinHeapItem> = BinaryHeap::new();
    let values = [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

    for &value in &values {
        heap.push(MinHeapItem(value));
    }

    assert_eq!(heap.len(), 16);

    // Rust's memory management is safe and does not allow simulating out-of-memory scenarios directly.
    // However, we can test the heap's behavior with a fixed set of values.

    for i in 0..16 {
        if let Some(MinHeapItem(val)) = heap.pop() {
            assert_eq!(val, i as i32);
        }
    }

    assert_eq!(heap.len(), 0);
}

fn main() {
    // Rust's test framework automatically discovers and runs tests.
    // No need for a manual test runner in `main`.
}
